package com.lun.swordtowardoffer2.c11;

public class SearchInsert {
	
	public int searchInsert(int[] nums, int target) {
		int left = 0;
		int right = nums.length - 1;
		
		while(left <= right) {
			int mid = left + (right - left) / 2;
			if(target <= nums[mid]) {
				if(mid == 0 || nums[mid - 1]  < target) {
					return mid;
				}
				right = mid - 1;
			}else {
				left = mid + 1;
			}
		}
				
		return nums.length;
	}
	
}
